﻿// 0830train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 给一块n * m的地块，相当于 n * m的二维数组，每个元素的值表示这个小地块的发电量；
 求在这块地上建立正方形的边长为 c的发电站，发电量满足目标电量 k 的地块数量

输入描述
第一行为四个按空格分隔的正整数，分别表示  n，m，c，k。后面 n 行整数，表示每个地块的发电量
输出描述
输出满足条件的地块数量

输入
2 5 2 6
1 3 4 5 8
2 3 6 7 1
输出
4

row_size 2 row_size-width
 */

class Solution01
{
public:
    Solution01(vector<vector<int>>&grid, int width, int target)
    {
        row_size = grid.size();
        col_size = grid[0].size();

        //建前缀和数组
        vector<vector<int>>pre_sum(row_size + 1, vector<int>(col_size+1));

        //写公式 r==0全0，c==0全0
        //row_size,col_size必须取到
        for (int r=1; r<=row_size; r++)
        {
	        for (int c=1; c<=col_size; c++)
	        {
                //[r-1][c]+[r][c-1]-[r-1][c-1]+grid[r-1][c-1]
                pre_sum[r][c] = pre_sum[r - 1][c] + pre_sum[r][c - 1] - pre_sum[r - 1][c - 1] + grid[r - 1][c - 1];

                //col_size
	        }
            //row_size
        }

        //计算width矩阵面积
        //row取值0 row_size-width
        int result = 0;
        for (int r=0; r<=row_size-width; r++)
        {
            for (int c=0; c<=col_size-width; c++)
            {
                int r_begin = r, r_end = r + width - 1, c_begin = c, c_end = c + width - 1;

                int bigger_ret = pre_sum[r_end + 1][c_end + 1];
                int row_ret = pre_sum[r_begin][c_end + 1];
                int col_ret = pre_sum[r_end + 1][c_begin];
                int repeat = pre_sum[r_begin][c_begin];

                int curr_ret = bigger_ret + repeat - row_ret - col_ret;

                if (curr_ret>=target)
                {
                    result += 1;
                }
            }
        }
        cout << result;
        //Solution01
    }
private:
    int row_size = 0, col_size = 0;
};


/*
系统发1+n张牌，每张牌上有一个整数
第一张给小明，后n张按照发牌顺序排成连续的一行
需要小明判断，后n张牌中，是否存在连续的若干张牌，其和可以整除小明手中牌上的数字

输入描述
第一行有两个整数n和m，空格隔开。m代表发给小明牌上的数字
第二行有n个数，代表后续发的n张牌上的数字，以空格隔开

输出描述
对每组输入，如果存在满足条件的连续若干张牌，则输出1；否则，输出0

输入
6 7
2 12 6 3 5 5
输出
1

输入
6 7（整除）
2 12 6 3 5 5
 */

class Solution02
{
public:
    Solution02(vector<int>&num_vec, int target)
    {
        int v_size = num_vec.size();

        //构建前缀和数组
        vector<int>pre_sum(v_size+1);
        pre_sum[0] = 0;
        for (int i=1; i<=v_size; i++)
        {
            pre_sum[i] = pre_sum[i - 1] + num_vec[i - 1];
        }

        int result = 0;
        //双重for循环
        for (int i=0; i<pre_sum.size(); i++)
        {
            for (int start=i+1; start<pre_sum.size(); start++)
            {
                int diff = pre_sum[start] - pre_sum[i];
                if (diff % target ==0)
                {
                    result = 1;
                    break;
                }
            }
            if (result == 1) break;
        }
        cout << result;
        //Solution02
    }
};


/*
 给定一个二维整数矩阵，要在这个矩阵中
 选出一个子矩阵，使得这个子矩阵内所有的数字和尽量大
我们把这个子矩阵称为 “和最大子矩阵”
子矩阵的选取原则，是原矩阵中一段相互连续的矩形区域

输入描述
输入的第一行包含两个整数N,M
(1 <= N, M <= 10)
表示一个 N 行 M 列的矩阵
下面有N行 每行有M个整数
同一行中每两个数字之间有一个空格
最后一个数字后面没有空格
所有的数字得在-1000 ~ 1000之间

输出描述
输出一行，一个数字。表示选出的“和最大子矩阵”内所有数字的和

3 4
-3 5 -1 5
2 4 -2 4
-1 3 -1 3
输出
20
 */
class Solution03
{
public:
    Solution03(vector<vector<int>>&grid)
    {
        row_size = grid.size();
        col_size = grid[0].size();

        //构建前缀和
        vector<vector<int>>pre_sum(row_size + 1, vector<int>(col_size + 1));

        //pre_sum[0][c]=0 pre_sum[r][0]=0
        for (int r=1; r<=row_size; r++)
        {
            for (int c=1; c<=col_size; c++)
            {
                //写公式
                //[r][c]=[r-1][c]+[r][c-1]-[r-1][c-1]+grid[r-1][c-1]
                pre_sum[r][c] = pre_sum[r - 1][c] + pre_sum[r][c - 1] - pre_sum[r - 1][c - 1] + grid[r - 1][c - 1];

            }

        }

        //“和最大子矩阵”内所有数字的和
        int result = INT_MIN;
        //遍历子矩阵
        for (int r_begin=0; r_begin<=row_size; r_begin++)
        {
	        for (int r_end=r_begin; r_end<row_size; r_end++)
	        {
                for (int c_begin=0;c_begin<=col_size; c_begin++)
                {
                    for (int c_end=c_begin; c_end<col_size; c_end++)
                    {
                        int outer_ret = pre_sum[r_end + 1][c_end + 1];
                        int top_ret = pre_sum[r_begin][c_end + 1];
                        int left_ret = pre_sum[r_end + 1][c_begin];
                        int repeat_ret = pre_sum[r_begin][c_begin];

                        int curr_ret = outer_ret + repeat_ret - top_ret - left_ret;

                        result = max(result, curr_ret);

                        //c_end
                    }
                    //c_begin
                }

                //r_end
	        }
            //r_begin
        }

        cout << result;
        //Solution03
    }
private:
    int row_size = 0, col_size = 0;
};


/*
 给定一个含有N个正整数的数组，求出有多少个连续区间（包括单个正整数）
 它们的和大于等于x

输入描述
第一行两个整数N x (0 < N <= 100000 ,0 <= x <= 10000000)
第二行有N个正整数（每个正整数小于等于100）。

输出描述
输出一个整数，表示所求的个数

输入
3 7
3 4 7
输出
4

3+4
4+7
3+4+7
7
这四组数据都是大于等于7的，所以答案为4
 */
class Solution04
{
public:
    Solution04(vector<int>&num_vec, int target)
    {
        //多少个连续区间,和大于等于target
        int v_size = num_vec.size();

        vector<int>pre_sum(v_size + 1);
        //构建前缀和数组
        pre_sum[0] = 0;
        for (int i=1;i<=v_size; i++)
        {
            pre_sum[i] = pre_sum[i - 1] + num_vec[i - 1];
        }

        int result = 0;

        for (int i=0; i<=v_size; i++)
        {
	        for (int start=i+1; start<=v_size; start++)
	        {
                int curr_sum = pre_sum[start] - pre_sum[i];

                if (curr_sum>=target)
                {
                    result += 1;
                }
	        }
        }
        cout << result;
	    //Solution04
    }
};

int main()
{
	{
        int v_size, target;
        cin >> v_size >> target;

        vector<int>num_vec(v_size);

        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution04 solu(num_vec, target);

        return 0;
	}
	{
/*
3 4
-3 5 -1 5
2 4 -2 4
-1 3 -1 3
*/
        int row_size, col_size;
        cin >> row_size >> col_size;
        vector<vector<int>>grid(row_size, vector<int>(col_size));

        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                cin >> grid[r][c];
            }
        }

        Solution03 solu(grid);

        return 0;
	}
	{
/*
6 7
2 12 6 3 5 5
 */
        
        int v_size, target;
        cin >> v_size >> target;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution02 solu(num_vec, target);

        return 0;
	}
    int row_size, col_size, width, target;
    cin >> row_size >> col_size >> width >> target;

    vector<vector<int>>grid(row_size, vector<int>(col_size));

    for (int r=0; r<row_size; r++)
    {
	    for (int c=0; c<col_size; c++)
	    {
            cin >> grid[r][c];
	    }
    }

    Solution01 solu(grid, width, target);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
